package FlowGraph.SSA;

import antlr.*;
import antlr.collections.AST;

import java.util.*;
import java.io.*;

import SymbolTable.*;
import FlowGraph.*;
import FlowGraph.Nodes.*;
import FlowGraph.EdgeInfo.*;
import JavaGrammar.TreeScanners.VarInfoCollector;
import JavaGrammar.*;
import FlowGraph.StatementInfo.*;
import db.ClassData;

//////////////////////////////////////////////////////////////////////////
//// SSA
/**
        * Atencao para o caso da expressao condicional ?. Vai ter dois
        defs para a mesma variavel.

        * No switch, se um caso continua outro, as variaveis herdadas
        terao definicoes novas. Por isso, o phi node logo no comeco
        do case vai ser removido.

        Nesta classe eu coleto as variaveis, e crio uma tabela de
hash onde a chave e um STEntry, e o dado e um objecto Varinfo.
Esse objeto guarda as informacoes referentes a cadeias de
definicao e uso.

@author Ivan Jeukens
@version v 0.1 31/01/2003
*/
public class SSA {

    public SSA(FlowGraph fg) {
        _fg = fg;

        FlowGraphNode fgnode = _fg.getSource();
        DominatorTreeNode dmroot = new DominatorTreeNode(fgnode);
        _dominatorTreeRoot = dmroot;
        DominatorTreeNode imnode = dmroot;
        fgnode = fgnode.getOutputNode(0);

        // com o null no terceiro parametro, processa inclusive o sink.
        _buildDominatorTree(fgnode, imnode, null);
        _buildDominanceFrontier(_fg.getSource());
        _collectVariableInfo();
        _placePhi();

        FlowGraphNode source = _fg.getSource();
        // Antes, muda os nomes dos parametros para nomeVar_0
        SymbolTable st = source.getSymbolTable();
        Iterator ite = st.iterator();
        while(ite.hasNext()) {
            STEntry entry = (STEntry) ite.next();
            // AST e um PARAMETER_DEF
            AST ast = entry.getNode();
            ast = ast.getFirstChild(); // modifiers
            ast = ast.getNextSibling(); // typespec
            ast = ast.getNextSibling(); // IDENT

            String name = ast.getText();
            String newname = new String(name +"_0");
            ast.setText(newname);
        }
        _rename(source);
    }

    ///////////////////////////////////////////////////////////////////
    ////                        public  methods                    ////

    // Dado um nome na forma ssa, retorna so o nome da variavel
    public static String getVarName(String name) {
        StringBuffer ret = new StringBuffer();
        char first = name.charAt(0);
        if(first == '_') ret.append("_");
        StringTokenizer st = new StringTokenizer(name, "_");
        while(st.countTokens() > 1) {
            ret.append(new String(st.nextToken()));
            if(st.countTokens() >= 2) ret.append("_");
        }
        return ret.toString();
    }

    // Dado um nome na forma ssa, retorna o indice da respectiva variavel
    public static int getVarIndex(String name) {
        StringTokenizer st = new StringTokenizer(name, "_");
        String tk = st.nextToken();
        while(st.hasMoreTokens()) {
            tk = st.nextToken();
        }
        Integer i = new Integer(tk);
        return i.intValue();
    }

    public DominatorTreeNode getDominatorTreeRoot() {
        return _dominatorTreeRoot;
    }

    public void debug(String basepath, int version) {
        try {
            String dotfile = new String(basepath + "/" +
                _fg.getMethodName() + "-v" + version + "-dom.dot");
            File f = new File(dotfile);
            FileOutputStream fs2 = new FileOutputStream(f);
            PrintStream ps2 = new PrintStream(fs2);

            StringBuffer buf = new StringBuffer("digraph \" " + _fg.getMethodName() +
              "\" {\n");
            buf.append("edge [ style = \"setlinewidth(1)\" ];\n");
            buf.append("graph [bb = \"0,0,1042,397\"];\n\n");

            if(_dominatorTreeRoot != null) {
                LinkedList process = new LinkedList();
                process.add(_dominatorTreeRoot);
                while(process.size() > 0) {
                    DominatorTreeNode node = (DominatorTreeNode) process.removeFirst();
                    FlowGraphNode fgn1 = node.getContainer();
                    buf.append(fgn1.hashCode() + " [label=\"" +
                        fgn1.typeToString() + "\"];\n");

                    Iterator ite = node.childrenIterator();
                    while(ite.hasNext()) {
                        DominatorTreeNode n2 = (DominatorTreeNode) ite.next();
                        FlowGraphNode fgn2 = n2.getContainer();
                        buf.append(fgn1.hashCode() + " -> " + fgn2.hashCode() + "\n");
                        process.add(n2);
                    }
                }
            }
            buf.append("}");
            ps2.print(buf.toString());
            ps2.close();

            // roda o dot no dom .dot
            Runtime run = Runtime.getRuntime();
            try {
               Process p = run.exec("dot " + dotfile + " -o t1");
               p.waitFor();
               p = run.exec("rm " + dotfile);
               p.waitFor();
               p = run.exec("mv t1 " + dotfile);
               p.waitFor();
            }
            catch(InterruptedException ex) {
                System.out.println("Exception : " + ex);
            }

            f = new File(new String(basepath + "/" +
                _fg.getMethodName() + "-v" + version + ".vars"));
            fs2 = new FileOutputStream(f);
            DataOutputStream dout = new DataOutputStream(fs2);

            dout.writeInt(_vars.size());
            Iterator ite = _vars.values().iterator();
            while(ite.hasNext()) {
                VariableInfo vinfo = (VariableInfo) ite.next();
                vinfo.debug(dout);
            }
            dout.close();
        }
        catch(IOException ex) {
            System.out.println(ex);
        }
    }

    public VariableInfo getVarInfo(STEntry entry) {
        return (VariableInfo) _vars.get(entry);
    }
    
    ///////////////////////////////////////////////////////////////////
    ////                        private  methods                    ////

    private void _rename(FlowGraphNode node) {
        LinkedList deflist = new LinkedList();
        _renamePhiStatements(node, deflist);

        switch(node.getType()) {
            case FlowGraphNode.BASIC_BLOCK: {
                BasicBlockNode bb = (BasicBlockNode) node;
                for(int i = 0;i < bb.statementsSize();i++) {
                    StatementInfo info = bb.getStatementInfo(i);
                    _renameUsesStatement(info, bb);
                    _renameDefsStatement(info, bb, deflist);
                }
            } break;

            case FlowGraphNode.FOR_BEGIN: {
                ForBeginNode fbeg = (ForBeginNode) node;
                StatementInfo info = fbeg.getConditionInfo();
                if(info != null) {
                    _renameUsesStatement(info, fbeg);
                    _renameDefsStatement(info, fbeg, deflist);
                }
            } break;

            default: {
                StatementInfo info = node.getStatementInfo();
                if(info != null) {
                    _renameUsesStatement(info, node);
                    _renameDefsStatement(info, node, deflist);
                }
            }
        }

        //System.out.println("Processando nos de saida de : " + 
        //        node);
        for(int i = 0;i < node.outputSize();i++) {
            FlowGraphNode outn = node.getOutputNode(i);
            //System.out.println("No de saida ->" + outn);

            int j = outn.getInputIndex(node);
            Iterator ite = outn.phiNodeIterator();
            while(ite.hasNext()) {
                PhiNode phinode = (PhiNode) ite.next();
                VariableInfo vinfo = phinode.getVariableInfo();

                int top = vinfo.getTopStack();
                phinode.setLabel(j, top);

                //System.out.println("Renaming arg " + j + " o phi " +
                //    phinode + " index = " + top);
                vinfo.addUseToChain(top, new VariableLocation(outn, 
                    phinode.getLabel(j), null, true));
            }
        }

        DominatorTreeNode dmnode = node.getDominatorTreeNode();
        Iterator ite = dmnode.childrenIterator();
        while(ite.hasNext()) {
            DominatorTreeNode child = (DominatorTreeNode) ite.next();
            FlowGraphNode childfg = child.getContainer();
            _rename(childfg);
        }

        for(int i = 0;i < deflist.size();i++) {
            VariableInfo varinfo = (VariableInfo) deflist.get(i);
            varinfo.popStack();
        }
    }

    private void _renameUsesStatement(StatementInfo info, FlowGraphNode node) {
        //System.out.println("Fazendo o rename uses do no " +
        //     node);
        Iterator ite = info.usedVarsIterator();
        while(ite.hasNext()) {
            VariableInfo vinfo = (VariableInfo) ite.next();
            //System.out.println("Variavel " + vinfo);

            int i = vinfo.getTopStack();
            LinkedList uses = info.getUses(vinfo);
            for(int k = 0;k < uses.size();k++) {
                AST vast = (AST) uses.get(k);
                String name = vast.getText();

                //System.out.println("Index e : " + i);
                //System.out.println("Name antes = " + name);

                String newname = new String(name +"_" + i);
                vast.setText(newname);

                //System.out.println("Name depois = " + newname);
                VariableLocation loc = new VariableLocation(node,
                    vast, info, false);

                //System.out.println("Vou adicionar o uso " + 
                //   vinfo + "_" + i + " location " + loc);
                vinfo.addUseToChain(i, loc);
                info.addIndexedVarUse(i, loc, vinfo);
            }
        }
    }

    private void _renamePhiStatements(FlowGraphNode node, LinkedList deflist) {
        Iterator ite = node.phiNodeIterator();
        while(ite.hasNext()) {
            PhiNode phi = (PhiNode) ite.next();
            VariableInfo varinfo = phi.getVariableInfo();

            deflist.add(varinfo);

            varinfo.incCount();
            int i = varinfo.getCount();
            varinfo.pushStack(i);
            phi.setDefLabel(i);

            varinfo.addDefToChain(i, new VariableLocation(node, 
                phi.getDefLabel(), null, true));
        }
    }

    private void _renameDefsStatement(StatementInfo info, FlowGraphNode node, 
            LinkedList deflist) {
        Iterator ite = info.definedVarsIterator();
        while(ite.hasNext()) {
            VariableInfo vinfo = (VariableInfo) ite.next();

            deflist.add(vinfo);

            // nova definicao
            vinfo.incCount();
            int i = vinfo.getCount();
            vinfo.pushStack(i);

            LinkedList defs = info.getDefs(vinfo);
            // Pode ter mais de um def quando for a expressao ternaria
            // de decisao ... cond? ex1 : ex2 ....
            if(defs.size() > 1) {
                // System.out.println("REnamedefs: defs size > 1 !!!");
            }
            for(int k = 0;k < defs.size();k++) {
                AST vast = (AST) defs.get(k);

                AST past = ((LinkedAST)vast).getParent();
                // case var++-> use, use, def
                if(past.getType() == JavaTokenTypes.POST_DEC ||
                   past.getType() == JavaTokenTypes.POST_INC) {

                }
                else
                if(past.getType() == JavaTokenTypes.DEC ||
                   past.getType() == JavaTokenTypes.INC) {

                }
                else {
                    String name = vast.getText();
                    String newname = new String(name + "_" + i);
                    vast.setText(newname);
                }

                VariableLocation defloc = new VariableLocation(node, vast, 
                    info, false);
                vinfo.addDefToChain(i, defloc);
                info.addIndexedVarDef(i, defloc, vinfo);

                // para o caso ++var, tem que adicionar mais um use.
                // COXA, mas funciona
                if(past.getType() == JavaTokenTypes.DEC ||
                   past.getType() == JavaTokenTypes.INC) {
                    VariableLocation useloc = new VariableLocation(node, vast, 
                        info, false);
                    vinfo.addUseToChain(i, useloc);
                    info.addIndexedVarUse(i, useloc, vinfo);
                }
            }
        }
    }

    private void _placePhi() {
        Iterator ite = _vars.values().iterator();
        while(ite.hasNext()) {
            VariableInfo varInfo = (VariableInfo) ite.next();

            Iterator defIte = varInfo.defSitesIterator();
            LinkedList newDefs = new LinkedList();
            while(defIte.hasNext()) {
                VariableLocation loc = (VariableLocation) defIte.next();

                FlowGraphNode fgnode = loc.getFGNode();
                _placePhiProcess(fgnode, newDefs, varInfo);

                while(newDefs.size() > 0) {
                    FlowGraphNode dmnode = (FlowGraphNode) newDefs.removeFirst();
                    _placePhiProcess(dmnode, newDefs, varInfo);
                }
            }
        }
    }

    private void _placePhiProcess(FlowGraphNode fgnode, LinkedList newDefs,
            VariableInfo varInfo) {
        Iterator dmfIte = fgnode.dominanceFrontierIterator();
        while(dmfIte.hasNext()) {
            FlowGraphNode dmnode = (FlowGraphNode) dmfIte.next();
            if(!dmnode.containsPhiNode(varInfo)) {
                PhiNode phi = new PhiNode(varInfo, dmnode.inputSize());

                STEntry entry = varInfo.getSTEntry();
                if(entry instanceof STLocalVariableEntry) {
                    // Verifica se na ST do no, a variavel esta definida.
                    if(dmnode.hasVar(entry)) {
                        dmnode.addPhiNode(phi);
                        if(!dmnode.definesVar(entry)) {
                            newDefs.add(dmnode);
                        }
                    }
                }
                else {
                    dmnode.addPhiNode(phi);
                    if(!dmnode.definesVar(entry)) {
                        newDefs.add(dmnode);
                    }
                }
            }
        }
    }

    private void _collectVariableInfo() {
        ClassData cinfo = _fg.getClassInfo();

        _vars = new HashMap();

        // Introduz uma definicao para as variaveis membros e para
        // os parametros.
        Iterator ite = cinfo.portsIterator();
        _addUndefinedDef(ite, _fg, cinfo);

        ite = cinfo.parametersIterator();
        _addUndefinedDef(ite, _fg, cinfo);

        ite = cinfo.variablesIterator();
        _addUndefinedDef(ite, _fg, cinfo);

        FlowGraphNode source = _fg.getSource();
        ite = source.symbolTableIterator();
        _addUndefinedDef(ite, _fg, cinfo);

        VarInfoCollector collector  = new VarInfoCollector();
        collector.setClassInfo(cinfo);
        collector.setVarsMap(_vars);

        ite = _fg.nodesIterator();
        while(ite.hasNext()) {
            FlowGraphNode fgnode = (FlowGraphNode) ite.next();
            collector.setFlowGraphNode(fgnode);
            collector.setStatementInfo(fgnode.getStatementInfo());
            try {
                switch(fgnode.getType()) {
                    case FlowGraphNode.METHOD_CALL: {
                        collector.statement(fgnode.getAbsTreeNode());
                    } break;

                    case FlowGraphNode.INNER_CLASS: break;

                    case FlowGraphNode.BASIC_BLOCK: {
                        BasicBlockNode bb = (BasicBlockNode) fgnode;
                        for(int i = 0;i < bb.statementsSize();i++) {
                            collector.setStatementInfo(bb.getStatementInfo(i));
                            collector.statement(bb.getStatement(i));
                        }
                    } break;

                    case FlowGraphNode.IF_BEGIN: {
                        IfBeginNode ifbeg = (IfBeginNode) fgnode;
                        collector.statement(ifbeg.getCondition());
                    } break;

                    case FlowGraphNode.FOR_BEGIN: {
                        ForBeginNode fbeg = (ForBeginNode) fgnode;
                        // collector.statement(fbeg.getInit());
                        collector.statement(fbeg.getCondition());
                        // collector.statement(fbeg.getIterator());
                    } break;
                    
                    case FlowGraphNode.SWITCH_BEGIN: {
                        SwitchBeginNode swbeg = (SwitchBeginNode) fgnode;
                        collector.statement(swbeg.getExpression());
                    } break;

                    case FlowGraphNode.WHILE_BEGIN: {
                        WhileBeginNode wbeg = (WhileBeginNode) fgnode;
                        collector.statement(wbeg.getCondition());
                    } break;

                    case FlowGraphNode.RETURN: {
                        ReturnNode retn = (ReturnNode) fgnode;
                        if(retn.getExpression() != null) {
                            collector.statement(retn.getExpression());
                        }
                    } break;

                    case FlowGraphNode.CATCH_BEGIN: {
                        CatchBeginNode cbeg = (CatchBeginNode) fgnode;
                        collector.statement(cbeg.getParameterAST());
                    } break;
                    
                    case FlowGraphNode.FOR_END:
                    case FlowGraphNode.THROW:
                    case FlowGraphNode.CONTINUE:
                    case FlowGraphNode.BREAK: break;

                    case FlowGraphNode.DO_CONDITION: {
                        DoConditionNode dcond = (DoConditionNode) fgnode;
                        collector.statement(dcond.getCondition());
                    } break;

                    case FlowGraphNode.SYNC_BEGIN: {
                        SyncBeginNode syncb = (SyncBeginNode) fgnode;
                        collector.statement(syncb.getExpression());
                    } break;

                    case FlowGraphNode.TRY_BEGIN: break;
                }
            }
            catch(RecognitionException ex) {
                System.out.println("collectVariableInfo: " + ex);
            }
        }
    }

    private void _addUndefinedDef(Iterator ite, FlowGraph fg, ClassData cinfo) {
        while(ite.hasNext()) {
            STEntry entry = (STEntry) ite.next();
            VariableInfo vinfo = new VariableInfo(entry, cinfo);
            _vars.put(entry, vinfo);

            VariableLocation loc = new VariableLocation(fg.getSource(), null,
                null, false);
            vinfo.addDefSite(loc);
        }
    }

    private void _buildDominanceFrontier(FlowGraphNode node) {
        DominatorTreeNode dmnode = node.getDominatorTreeNode();

        if(dmnode == null) return;   // O sink.

        // Calcula recursivamente o DFup para o no
        Iterator children = dmnode.childrenIterator();
        while(children.hasNext()) {
            DominatorTreeNode child = (DominatorTreeNode) children.next();
            FlowGraphNode fgnode = child.getContainer();
            _buildDominanceFrontier(fgnode);
            
            Iterator ite = fgnode.dominanceFrontierIterator();
            while(ite.hasNext()) {
                FlowGraphNode fgnode2 = (FlowGraphNode) ite.next();
                DominatorTreeNode dmnode2 = fgnode2.getDominatorTreeNode();
                if(dmnode != dmnode2.getParent()) {
                    node.addToDominanceFrontier(fgnode2);
                }
            }
        }

        // Calcula o DFlocal
        for(int i = 0;i < node.outputSize();i++) {
            FlowGraphNode fgnode2 = node.getOutputNode(i);
            if(fgnode2 == _fg.getSink()) continue;
            
            DominatorTreeNode dmnode2 = fgnode2.getDominatorTreeNode();
            if(dmnode != dmnode2.getParent()) {
                node.addToDominanceFrontier(fgnode2);
            }
        }
    }
    
    private DominatorTreeNode _buildDominatorTree(FlowGraphNode fgnode,
            DominatorTreeNode imnode, FlowGraphNode stopNode) {
        
        while(fgnode != null && fgnode.getType() != FlowGraphNode.SINK &&
                fgnode != stopNode) {
            switch(fgnode.getType()) {
                case FlowGraphNode.METHOD_CALL:
                case FlowGraphNode.INNER_CLASS:
                case FlowGraphNode.BASIC_BLOCK: {
                    DominatorTreeNode dmnode = new DominatorTreeNode(fgnode);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);

                    // Se tiver edge de exception nao importa. Essa aresta
                    // eu lido durante o catch
                    fgnode = _getNonExceptionOutput(fgnode);
                    imnode = dmnode;
                } break;

                case FlowGraphNode.IF_BEGIN: {
                    DominatorTreeNode dmnode = new DominatorTreeNode(fgnode);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode; // passa ser o ifbegin

                    IfBeginNode beg = (IfBeginNode) fgnode;
                    IfEndNode end = (IfEndNode) beg.getIfEnd();

                    if(end != null && end.hasThen() && !end.hasElse()) {
                        FlowGraphNode branch = beg.getThenNode();
                        DominatorTreeNode ret = _buildDominatorTree(branch,
                            imnode, end);

                        branch = beg.getElseNode();
                        if(branch != null) {
                            _buildDominatorTree(branch, imnode, end);
                        }

                        dmnode = new DominatorTreeNode(end);
                        dmnode.setParent(ret);
                        ret.addChild(dmnode);

                        fgnode = _getNonExceptionOutput(end);
                        imnode = dmnode;
                    }
                    else
                    if(end != null && end.hasElse() && !end.hasThen()) {
                        FlowGraphNode branch = beg.getElseNode();
                        DominatorTreeNode ret = _buildDominatorTree(branch, 
                            imnode, end);

                        branch = beg.getThenNode();
                        if(branch != null) {
                            _buildDominatorTree(branch, imnode, end);
                        }

                        dmnode = new DominatorTreeNode(end);
                        dmnode.setParent(ret);
                        ret.addChild(dmnode);

                        fgnode = _getNonExceptionOutput(end);
                        imnode = dmnode;
                    }
                    else
                    // tem o dois
                    if(end != null) {
                        FlowGraphNode branch = beg.getThenNode();
                        if(branch != null) {
                            _buildDominatorTree(branch, imnode, end);
                        }
                        branch = beg.getElseNode();
                        if(branch != null) {
                            _buildDominatorTree(branch, imnode, end);
                        }
                        dmnode = new DominatorTreeNode(end);
                        dmnode.setParent(imnode);
                        imnode.addChild(dmnode);

                        fgnode = _getNonExceptionOutput(end);
                        imnode = dmnode;
                    }
                    else {
                        FlowGraphNode branch = beg.getThenNode();
                        if(branch != null) {
                            // vai parar no sink de qualquer forma
                            _buildDominatorTree(branch, imnode, null);
                        }
                        branch = beg.getElseNode();
                        if(branch != null) {
                            _buildDominatorTree(branch, imnode, null);
                        }
                        fgnode = null;
                        imnode = null;
                    }
                } break;

                case FlowGraphNode.FOR_BEGIN: {
                    ForBeginNode beg = (ForBeginNode) fgnode;
                    ForEndNode end = beg.getForEnd();
                    FlowGraphNode cont = beg.getContinueNode();
                    
                    DominatorTreeNode dmnode = new DominatorTreeNode(beg);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode;

                    if(cont != beg) {
                        // os caminhos que nao sao atraves do backedge e
                        // tratado no no break.
                        _buildDominatorTree(cont, imnode, beg);
                    }

                    dmnode = new DominatorTreeNode(end);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);

                    imnode = dmnode;
                    fgnode = _getNonExceptionOutput(end);
                } break;

                case FlowGraphNode.WHILE_BEGIN: {
                    WhileBeginNode beg = (WhileBeginNode) fgnode;
                    WhileEndNode end = beg.getWhileEnd();
                    FlowGraphNode cont = beg.getContinueNode();

                    DominatorTreeNode dmnode = new DominatorTreeNode(beg);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode;

                    if(cont != beg) {
                        _buildDominatorTree(cont, imnode, beg);
                    }

                    dmnode = new DominatorTreeNode(end);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);

                    imnode = dmnode;
                    fgnode = _getNonExceptionOutput(end);
                } break;
                
                case FlowGraphNode.THROW:
                case FlowGraphNode.RETURN:
                case FlowGraphNode.CONTINUE:
                case FlowGraphNode.BREAK: {
                    DominatorTreeNode dmnode = new DominatorTreeNode(fgnode);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);

                    return null;
                }

                case FlowGraphNode.DO_BEGIN: {
                    DoBeginNode beg = (DoBeginNode) fgnode;
                    DoConditionNode cond = beg.getConditionNode();
                    DoEndNode end = beg.getDoEnd();

                    DominatorTreeNode dmnode = new DominatorTreeNode(beg);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode;

                    fgnode = beg.getOutputNode(0);
                    DominatorTreeNode ret = _buildDominatorTree(fgnode, imnode, 
                        cond);

                    DominatorTreeNode conddmnode = new DominatorTreeNode(cond);
                    if(cond.inputSize() == 0) {
                        // se nao tiver input, e porque no bloco tinha return e
                        // break.
                        conddmnode.setParent(null);
                    }
                    else
                    if(cond.inputSize() == 1) {
                        // se so tem um input, entao ele e o dom
                        FlowGraphNode n = cond.getInputNode(0);
                        DominatorTreeNode idm = n.getDominatorTreeNode();
                        conddmnode.setParent(idm);
                        idm.addChild(conddmnode);
                    }
                    else {
                        // se tem mais de um input, tem que achar que domina
                        // os dois. No caso extremo, vai ser o do begin.
                        LinkedList nodes = new LinkedList();
                        for(int j = 0;j < cond.inputSize();j++) {
                            FlowGraphNode innode = (FlowGraphNode) cond.getInputNode(j);
                            nodes.add(innode.getDominatorTreeNode());
                        }
                        DominatorTreeNode retdmnode = _findCommonDominator(nodes);

                        retdmnode.addChild(conddmnode);
                        conddmnode.setParent(retdmnode);
                    }

                    dmnode = new DominatorTreeNode(end);
                    if(end.inputSize() > 1) {
                        // Se tem mais que um input, teve break no loop.
                        LinkedList nodes = new LinkedList();
                        for(int j = 0;j < end.inputSize();j++) {
                            FlowGraphNode innode = (FlowGraphNode) end.getInputNode(j);
                            nodes.add(innode.getDominatorTreeNode());
                        }
                        DominatorTreeNode retdmnode = _findCommonDominator(nodes);

                        retdmnode.addChild(dmnode);
                        dmnode.setParent(retdmnode);
                    }
                    else {
                        dmnode.setParent(conddmnode);
                        conddmnode.addChild(dmnode);
                    }
                    imnode = dmnode;
                    fgnode = end.getOutputNode(0);
                } break;

                case FlowGraphNode.SWITCH_BEGIN: {
                    SwitchBeginNode beg = (SwitchBeginNode) fgnode;
                    SwitchEndNode end = beg.getSwitchEnd();

                    DominatorTreeNode dmnode = new DominatorTreeNode(beg);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode;

                    // processa cada case do switch
                    for(int i = 0;i < beg.outputSize();i++) {
                        FlowGraphNode cnode = beg.getOutputNode(i);

                        // Verifica se esse no ja foi processado. Isso
                        // ocorre quando tem uma sequencia de cases sem
                        // break...
                        if(cnode.getDominatorTreeNode() != null) {
                            // Isso aqui depende do seguinte: o branch sem
                            // o break tem que ser processado antes. Ai
                            // So corrijo o primeiro no
                            DominatorTreeNode cdmnode = cnode.getDominatorTreeNode();
                            DominatorTreeNode parent = cdmnode.getParent();
                            parent.removeNode(cdmnode);

                            imnode.addChild(cdmnode);
                            cdmnode.setParent(imnode);

                            continue;
                        }
                        _buildDominatorTree(cnode, imnode, end);
                    }

                    // So tem um break. Entao ele e o dominator
                    dmnode = new DominatorTreeNode(end);
                    if(end.inputSize() == 1) {
                        FlowGraphNode bnode = end.getInputNode(0);
                        imnode = bnode.getDominatorTreeNode();
                        dmnode.setParent(imnode);
                        imnode.addChild(dmnode);
                    }
                    else {
                        // Senao, quem domina e o switch begin
                        dmnode.setParent(imnode);
                        imnode.addChild(dmnode);
                    }
                    imnode = dmnode;
                    fgnode = end.getOutputNode(0);
                } break;

                case FlowGraphNode.SYNC_BEGIN: {
                    SyncBeginNode beg = (SyncBeginNode) fgnode;
                    SyncEndNode end = beg.getSyncEnd();

                    DominatorTreeNode dmnode = new DominatorTreeNode(beg);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode;

                    fgnode = beg.getOutputNode(0);
                    imnode = _buildDominatorTree(fgnode, imnode, end);

                    if(end != null) {
                        dmnode = new DominatorTreeNode(end);
                        dmnode.setParent(imnode);
                        imnode.addChild(dmnode);

                        imnode = dmnode;
                        fgnode = end.getOutputNode(0);
                    }
                    else {
                        fgnode = null;
                        imnode = null;
                    }
                } break;

                case FlowGraphNode.TRY_BEGIN: {
                    TryBeginNode tbeg = (TryBeginNode) fgnode;
                    TryEndNode end = tbeg.getTryEnd();

                    DominatorTreeNode dmnode = new DominatorTreeNode(tbeg);
                    dmnode.setParent(imnode);
                    imnode.addChild(dmnode);
                    imnode = dmnode;
                    
                    // Processa o corpo do try. Eu nao considero
                    // as arestas de exception
                    fgnode = _getNonExceptionOutput(tbeg);
                    DominatorTreeNode bodydm = _buildDominatorTree(fgnode, imnode, end);

                    // Processa cada branch catch
                    for(int i = 0;i < tbeg.catchSize();i++) {
                        CatchBeginNode catchNode = tbeg.getCatch(i);
                        DominatorTreeNode catchdm;
                        if(catchNode.inputSize() > 0) {
                            LinkedList ll = new LinkedList();
                            for(int j = 0;j < catchNode.inputSize();j++) {
                                ll.add(catchNode.getInputNode(j).getDominatorTreeNode());
                            }
                            DominatorTreeNode parent = _findCommonDominator(ll);
                            catchdm = new DominatorTreeNode(catchNode);
                            catchdm.setParent(parent);
                            parent.addChild(catchdm);
                        }
                        else {
                            catchdm = new DominatorTreeNode(catchNode);
                        }
                        CatchEndNode cend = catchNode.getCatchEnd();
                        
                        DominatorTreeNode dmret = _buildDominatorTree(
                                catchNode.getOutputNode(0), catchdm, cend);

                        // Se tiver um throw ou return, nao tem end
                        if(cend != null) {   
                            DominatorTreeNode cenddm = new DominatorTreeNode(cend);
                            cenddm.setParent(dmret);
                            dmret.addChild(cenddm);
                        }
                    }
                    LinkedList ll = new LinkedList();
                    // O try end
                    if(end != null) {
                        // Tem que ser assim, pois as vezes o corpo tem return. Entao,
                        // nao da pra considerar so as cabecas dos catch...
                        for(int i = 0;i < end.inputSize();i++) {
                            FlowGraphNode n = end.getInputNode(i);
                            ll.add(n.getDominatorTreeNode());
                        }
                    }

                    /*
                    for(int i = 0;i < tbeg.catchSize();i++) {
                        DominatorTreeNode p = tbeg.getCatch(i).getDominatorTreeNode().getParent();
                        if(p == null) {
                            System.err.println("Pai do dominator do catch ta null");
                        }
                        else  {
                            ll.add(p);
                        }
                    }*/

                    DominatorTreeNode parent;
                    if(ll.size() == 0) {
                        parent = null;
                    }
                    else {
                        parent = _findCommonDominator(ll);
                    }
                    // O Try pode nao ter end quando o corpo sai pro sink, e nao
                    // tem catch.
                    DominatorTreeNode enddm = null;
                    if(end != null) {
                        enddm = new DominatorTreeNode(end);
                        if(parent == null) {
                            // pode ser try sem catch
                            if(tbeg.catchSize() == 0) {
                                bodydm.addChild(enddm);
                                enddm.setParent(bodydm);
                            }
                            // Nesse caso, e porque os catch nao estao ligados
                            // ao corpo do try. Isso nao e suportado.
                        }
                        else {
                            parent.addChild(enddm);
                            enddm.setParent(parent);
                        }
                    }

                    // O Finally pode ter arestas vindas diretamente
                    // do corpo do try
                    FinallyBeginNode fbeg = tbeg.getFinally();
                    if(fbeg != null) {
                        LinkedList finput = new LinkedList();
                        for(int i = 0;i < fbeg.inputSize();i++) {
                            FlowGraphNode fn = fbeg.getInputNode(i);
                            finput.add(fn.getDominatorTreeNode());
                        }
                        parent = _findCommonDominator(finput);

                        dmnode = new DominatorTreeNode(fbeg);
                        dmnode.setParent(parent);
                        parent.addChild(dmnode);
                        imnode = dmnode;

                        FinallyEndNode fend = fbeg.getFinallyEnd();
                        imnode = _buildDominatorTree(fbeg.getOutputNode(0),
                            imnode, fend);

                        dmnode = new DominatorTreeNode(fend);
                        dmnode.setParent(imnode);
                        imnode.addChild(dmnode);

                        fgnode = fend.getOutputNode(0);
                        imnode = dmnode;
                    }
                    else {
                        if(end != null) {
                            imnode = enddm;
                            fgnode = end.getOutputNode(0);
                        }
                        else {
                            imnode = null;
                            fgnode = null;
                        }
                    }
                } break;
 
                default: {
                    System.out.println("BuildDominatorTree: " +
                        "Um tipo de no nao processado: " + fgnode);
                }
            }
        }

        return imnode;
    }

    // Dado um conjunto de nos de uma arvore, descobre um no que domina
    // todos eles.
    private DominatorTreeNode _findCommonDominator(LinkedList nodes) {
        DominatorTreeNode ret = (DominatorTreeNode) nodes.get(0);
        for(int i = 1;i < nodes.size();i++) {
            DominatorTreeNode dmnode = (DominatorTreeNode) nodes.get(i);
            if(ret.dominates(dmnode)) {
                continue;
            }
            else {
                while(ret.getParent() != null) {
                    ret = ret.getParent();
                    if(ret.dominates(dmnode)) {
                        break;
                    }
                }
                if(ret.getParent() == null) return ret;
            }
        }
        return ret;
    }

    // Retorna o primeiro no de output que nao ta ligado por uma aresta
    // de exception
    private FlowGraphNode _getNonExceptionOutput(FlowGraphNode fgnode) {
        Iterator ite = fgnode.outputEdgesIterator();
        while(ite.hasNext()) {
            FlowGraphEdge edge = (FlowGraphEdge) ite.next();
            EdgeInfo info = edge.getEdgeInfo();
            if(info != null && info.getType() == EdgeInfo.EXCEPTION) continue;

            return edge.getTo();
        }
        return null;
    }

    private void _printDominatorTree(DominatorTreeNode node) {
        LinkedList process = new LinkedList();
        process.add(node);
        while(process.size() > 0) {
            DominatorTreeNode dmnode = (DominatorTreeNode) process.removeFirst();
            System.out.println(dmnode.toString());
            Iterator ite = dmnode.childrenIterator();
            while(ite.hasNext()) {
                DominatorTreeNode dmn = (DominatorTreeNode) ite.next();
                process.addLast(dmn);
            }
        }
    }

    ///////////////////////////////////////////////////////////////////
    ////                      public  variables                    ////

    private FlowGraph _fg;

    private DominatorTreeNode _dominatorTreeRoot;

    // As varinfo. A chave e uma STEntry
    private HashMap _vars;
}
